#ifndef _BINARY_SEARCH_ARRAY_H_
#define _BINARY_SEARCH_ARRAY_H_

template <typename V, typename K>
struct DummyKeyExtractor;

template <typename K, typename V = K, typename _Pr = less<K>, typename _Ex = DummyKeyExtractor<V, K> >
class BinarySearchArray {
public:
	typedef K key_type;
	typedef V value_type;

	class iterator {
		BinarySearchArray* _array;
		size_t _pos;
	public:
		iterator(): _array(0), _pos(0) {}

		iterator(BinarySearchArray* arr, size_t pos): _array(arr), _pos(pos) {}

		// default copy, assign, deconstruction are fine

		// algorithmic
		iterator& operator++() {
			assert(_pos < _array->size());
			++_pos;
			return *this;
		}

		iterator operator++(int) { iterator tmp(*this); ++(*this); return tmp; }

		// happy dereferencer
		value_type& operator*() { return (*_array)[_pos]; }

		value_type* operator->() { return &((*_array)[_pos]); }

		// compare
		bool operator==(const iterator& other) const { return _array == other._array && _pos == other._pos; }
		bool operator!=(const iterator& other) const { return _array != other._array || _pos != other._pos; }
	};

	class const_iterator {
		const BinarySearchArray* _array;
		size_t _pos;
	public:
		const_iterator(): _array(0), _pos(0) {}

		const_iterator(const BinarySearchArray* arr, size_t pos): _array(arr), _pos(pos) {}

		// default copy, assign, deconstruction are fine
		const_iterator(const const_iterator& other): _array(other._array), _pos(other._pos) {}

		const_iterator(const iterator& other): _array(other._array), _pos(other._pos) {}

		// algorithmic
		const_iterator& operator++() {
			assert(_pos < _array->size());
			++_pos;
			return *this;
		}

		iterator operator++(int) { iterator tmp(*this); ++(*this); return tmp; }

		// happy dereferencer
		const value_type& operator*() const { return (*_array)[_pos]; }

		const value_type* operator->() const { return &((*_array)[_pos]); }

		// compare
		bool operator==(const const_iterator& other) const { return _array == other._array && _pos == other._pos; }
		bool operator!=(const const_iterator& other) const { return _array != other._array || _pos != other._pos; }
	};

private:
	_Pr m_key_less;
	_Ex m_key_extr;
	value_type* m_dataArray;
	int m_size; // capacity
	int m_next; // next available index, actual size
public:
	BinarySearchArray():m_size(0), m_dataArray(0), m_next(0) {}
	explicit BinarySearchArray(int size): m_size(size), m_dataArray(0), m_next(0) {
		if (size > 0) {
			m_dataArray((value_type*)malloc(sizeof(value_type)*size));
		}
	}

	virtual ~BinarySearchArray() {
		if (m_dataArray == NULL) { return; }
		for (--m_next; m_next >= 0; --m_next) {
			(m_dataArray + m_next)->~value_type();
		}
		free(m_dataArray);
	}

	iterator begin() { return iterator(this, 0); }
	iterator end() { return iterator(this, m_next); }
	const_iterator begin() const { return const_iterator(this, 0); }
	const_iterator end() const { return const_iterator(this, m_next); }

	pair<iterator, bool> insert(const value_type& val) {
		assert(m_next < m_size);
		assert(m_next == 0 || m_key_less( m_key_extr(m_dataArray[m_next - 1]), m_key_extr(val) ) );
		new(m_dataArray + m_next) value_type(val);
		return make_pair(iterator(this, m_next++), true);
	}

	size_t erase(const key_type& key) { return 0; }

	iterator find(const key_type& key) {
		unsigned int p = m_next >> 1;
		unsigned int l = 0;
		unsigned int r = m_next;
		// [l, r)
		while (p < r) {
			if (m_key_less(m_key_extr(m_dataArray[p]), key)) {
				l = p + 1;
			} else if (m_key_less(key, m_key_extr(m_dataArray[p]))) {
				r = p;
			} else { // ==
				return iterator(this, p);
			}
			p = l + ((r - l) >> 1);
		} // while (p < r)
		return end();
	}

	value_type& operator[](int i) { return m_dataArray[i]; }

	const value_type& operator[](int i) const { return m_dataArray[i]; }

	size_t size() const { return m_next; }

	size_t capacity() const { return m_size; }

	bool empty() const {
		return !m_size;
	}

	// only available after just created object with non-param constructor
	void initialize(size_t newSize) {
		if (m_dataArray == NULL && newSize != 0) {
			m_dataArray = (value_type*)malloc(sizeof(value_type) * newSize);
			assert(m_dataArray);
			m_size = newSize;
		}
	}
};

#endif